﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BacktrackingCode
{
    //棋盘问题
    class CheckerBoard
    {
        //======================================力扣51 N皇后
        //如何将n个皇后放置在n*n的棋盘上，并且是皇后彼此之前不能攻击
        List<IList<string>> result;

        public IList<IList<string>> SolveNQueens(int n)
        {
            result = new List<IList<string>>();
            List<string> chessboard = new List<string>(n);
            for(int i = 0;i<n;i++)
            {
                string tem = "";
                for(int j = 0;j<n;j++)
                {
                    tem += '.';
                }
                chessboard.Add(tem);
            }
            BackTracking(n, 0, chessboard);
            return result;

        }
        void BackTracking(int n, int row, List<string> chessboard)
        {//row记录遍历到第几层
            //棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度
            if (n == row)
            {
                result.Add(new List<string>(chessboard));
                return;
            }
            
            for(int i = 0;i<n;i++)
            {
                if(isVaild(row, i, chessboard, n))
                {
                    char[] arr = chessboard[row].ToArray();
                    arr[i] = 'Q';
                    chessboard[row] = new string(arr);
                    BackTracking(n, row + 1, chessboard);
                    arr[i] = '.';
                    chessboard[row] = new string(arr);
                }
            }
        }
        bool isVaild(int row, int col, List<string> chessboard, int n)
        {//不需要检查行
            //检查列
            for(int i = 0;i<row;i++)
            {
                if (chessboard[i][col] == 'Q')
                    return false;
            }
            //检查45度线
            for(int i = row - 1,j = col - 1;i >= 0 && j >= 0;i--,j--)
            {
                if (chessboard[i][j] == 'Q')
                    return false;
            }
            //检查135度线
            for(int i = row - 1,j = col + 1;i>= 0 && j<n;i--,j++)
            {
                if (chessboard[i][j] == 'Q')
                    return false;
            }
            return true;
        }

        //=============================================力扣37 解数独
        //编写一个程序，通过填充空格来解决数独问题
        //数独规则：1.数字1-9在每行和每列都只能出现一次。2.数字1-9在每一个 粗实线分割的3*3的九宫格内只能出现一次
        //数独部分空格内已填入数字，空白格用'.'表示
        public void SolveSudoku(char[][] board)
        {
            BackTracking_2(board);
        }
        bool BackTracking_2(char[][] board)
        {
            for(int i = 0;i<board.Length;i++)// 遍历行
            {
                for(int j = 0;j<board[0].Length;j++)// 遍历列
                {
                    if (board[i][j] != '.')
                        continue;
                    for(char k = '1';k <='9';k++) // (i, j) 这个位置放k是否合适
                    {
                        if(IsVaild(i, j, k, board))
                        {
                            board[i][j] = k;// 放置k
                            if (BackTracking_2(board))// 如果找到合适一组立刻返回
                                return true;
                            board[i][j] = '.';// 回溯，撤销k
                        }
                    }
                    return false;// 9个数都试完了，都不行，那么就返回false
                }
            }
            return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
        }
        bool IsVaild(int row, int col, int val, char[][] board)
        {
            for (int i = 0; i < 9; i++)
            {//判断行里有重复
                if (board[row][i] == val)
                    return false;
            }
            for (int j = 0; j < 9; j++)
            {// 判断列里是否重复
                if (board[j][col] == val)
                    return false;
            }
            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;
            for(int i = startRow;i<startRow+3;i++)
            {
                for (int j = startCol; j < startCol + 3; j++)
                {
                    if (board[i][j] == val)
                    {
                        return false;
                    }
                }
            }
            return true;
        }


    }
}
